#include <iostream>
#include <queue>

#include "common/utils.hpp"

int result = 0;
int maxDepth = INT_MIN;

void traversal(TreeNode* node, int depth) {
    if (node->left == nullptr && node->right == nullptr) {
        if (depth > maxDepth) {
            result = node->val;
            maxDepth = depth;
            return;
        }
    }

    if (node->left != nullptr) {
        depth++;
        traversal(node->left, depth);
        depth--;
    }

    if (node->right != nullptr) {
        depth++;
        traversal(node->right, depth);
        depth--;
    }
}

int findBottomLeftValue(TreeNode* root) {
    traversal(root, 0);
    return result;
}

extern TreeNode* commonRoot;

int main() {
    int ret = findBottomLeftValue(commonRoot);
    std::cout << "res: " << ret << "\n";
}